"""
@Project ：Python_learning 
@File    ：76.最小覆盖字符串.py
@Author  ：zhupp
@Date    ：2024/12/15 18:01 
"""
import collections


def isContains(cur_map, t_map):
    for key in t_map:
        if cur_map[key] < t_map[key]:
            return False
    return True


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_map = collections.Counter(t)
        win_map = {}
        # 初始化win_map，让里面的key包含tmap中的key
        for key in t_map:
            if key not in win_map:
                win_map[key] = 0
        #初始化左指针
        left = 0
        res = ""
        min_len = len(s) + 1
        for right in range(len(s)):
            # 让右边界移动使窗口包含所需元素
            if s[right] in win_map:
                win_map[s[right]] += 1
            while isContains(win_map,t_map):
                if min_len > right - left + 1:
                    min_len = right - left + 1
                    res = s[left : right + 1]
                # 判断左指针元素是否在窗口中，让该元素对应的个数减一
                if s[left] in win_map:
                    win_map[s[left]] -= 1
                # 左边界向右移
                left += 1
        return res